home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3412 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.4 KB  |  96 lines
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 28 Jan 1996 11:11:44 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4eghpgINNn5c@keats.ugrad.cs.ubc.ca>
  8. References: <4e61iu$p6e@villa.fc.net>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4e61iu$p6e@villa.fc.net>,
  12. Avinash Chopde <avinash@paranoia.com> wrote:
  13. >[And no, this is not for a homework exercise.]
  14. >[BTW, the non-abridged C FAW at http://www.eskimo.com/~scs/C-faq.top.html
  15. >does not seem to be accessible??]
  16. >
  17. >I am trying to find out what could be the fastest way to compute
  18. >the position of the highest bit in any given integer -- basically, the
  19. >logarithm to the base 2 of any number.
  20. >
  21. >Simplistically, one could do :
  22. >logbase2(int x)
  23. >{
  24. >    if (IS_SET_BIT_31(x)) return 31;
  25. >    if (IS_SET_BIT_30(x)) return 30;
  26. >    etc.
  27. >}
  28. >
  29. >An improvement would be to check for BITS_31_16 and BITS_15_0 at first, and
  30. >then check for BITS_31_24, and BITS_23_16, etc .. (divide problem in half
  31. >at each stage).
  32. >
  33. >Any thoughts or other ideas?
  34.  
  35. I did something like this a while ago.
  36.  
  37. The following is a macro which can help you choose the size of an array to fit
  38. a given number of elements such that the array will have a power of two size
  39. (good for hashing, or circular lists for example).
  40.  
  41. /* C macro to round a number up to the nearest power of two */
  42.  
  43. #ifndef _ROUND_H
  44. #define _ROUND_H
  45.  
  46. #define RP2(X) (                                                           \
  47.   (((X)-1) & 0x40000000) ? (0x80000000) : (                                \
  48.    (((X)-1) & 0x20000000) ? (0x40000000) : (                               \
  49.     (((X)-1) & 0x10000000) ? (0x20000000) : (                              \
  50.      (((X)-1) & 0x08000000) ? (0x10000000) : (                             \
  51.       (((X)-1) & 0x04000000) ? (0x08000000) : (                            \
  52.        (((X)-1) & 0x02000000) ? (0x04000000) : (                           \
  53.         (((X)-1) & 0x01000000) ? (0x02000000) : (                          \
  54.          (((X)-1) & 0x00800000) ? (0x01000000) : (                         \
  55.           (((X)-1) & 0x00400000) ? (0x00800000) : (                        \
  56.            (((X)-1) & 0x00200000) ? (0x00400000) : (                       \
  57.             (((X)-1) & 0x00100000) ? (0x00200000) : (                      \
  58.              (((X)-1) & 0x00080000) ? (0x00100000) : (                     \
  59.               (((X)-1) & 0x00040000) ? (0x00080000) : (                    \
  60.                (((X)-1) & 0x00020000) ? (0x00040000) : (                   \
  61.                 (((X)-1) & 0x00010000) ? (0x00020000) : (                  \
  62.                  (((X)-1) & 0x00008000) ? (0x00010000) : (                 \
  63.                   (((X)-1) & 0x00004000) ? (0x00008000) : (                \
  64.                    (((X)-1) & 0x00002000) ? (0x00004000) : (               \
  65.                     (((X)-1) & 0x00001000) ? (0x00002000) : (              \
  66.                      (((X)-1) & 0x00000800) ? (0x00001000) : (             \
  67.                       (((X)-1) & 0x00000400) ? (0x00000800) : (            \
  68.                        (((X)-1) & 0x00000200) ? (0x00000400) : (           \
  69.                         (((X)-1) & 0x00000100) ? (0x00000200) : (          \
  70.                          (((X)-1) & 0x00000080) ? (0x00000100) : (         \
  71.                           (((X)-1) & 0x00000040) ? (0x00000080) : (        \
  72.                            (((X)-1) & 0x00000020) ? (0x00000040) : (       \
  73.                             (((X)-1) & 0x00000010) ? (0x00000020) : (      \
  74.                              (((X)-1) & 0x00000008) ? (0x00000010) : (     \
  75.                               (((X)-1) & 0x00000004) ? (0x00000008) : (    \
  76.                                (((X)-1) & 0x00000002) ? (0x00000004) : (   \
  77.                                 (((X)-1) & 0x00000001) ? (0x00000002) : (  \
  78.                                   0x00000001                               \
  79. ))))))))))))))))))))))))))))))))
  80.  
  81.  
  82. #endif
  83.  
  84. >Thanks!
  85.  
  86. It essentially does your "is set bit" thing, except that because it is a
  87. macro, when you use it with a constant argument it will optimize nicely to a
  88. single load instruction that just fetches the right value. Great for
  89. compile-time dependencies.
  90.  
  91. To adapt it to return the bit position, you have to do a little editing, while
  92. maintaing the essential structure. :)
  93.  
  94. -- 
  95.  
  96.